#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
    char c=getchar();
    ll x=0,k=1;
    while(c<'0'||c>'9'){
        if(c=='-') k=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*k;
}
ll T,n,a[200001],ans;
ll f[2001][2][2001];
bool col[200001];
void dfs(int dep){
    if(dep>n){
        ll sum=0;
        for(int i=1;i<=n;i++){
            for(int j=i-1;j>=1;j--){
                if(col[j]==col[i]){
                    if(a[j]==a[i]) sum+=a[i];
                    break;
                }
            }
        }
        ans=max(sum,ans);
        return;
    }
    col[dep]=1;
    dfs(dep+1);
    col[dep]=0;
    dfs(dep+1);
    return;
}
void solve1(){
    memset(f,0,sizeof(f));
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            f[i+1][0][j]=
                max(f[i+1][0][j],
                f[i][0][j]+((a[i+1]==a[i])? a[i+1]:0));
            f[i+1][0][i]=
                max(f[i+1][0][i],
                f[i][1][j]+((a[i+1]==a[j])? a[i+1]:0));
            f[i+1][1][j]=
                max(f[i+1][1][j],
                f[i][1][j]+((a[i+1]==a[i])? a[i+1]:0));
            f[i+1][1][i]=
                max(f[i+1][1][i],
                f[i][0][j]+((a[i+1]==a[j])? a[i+1]:0));
        }
    }
    ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,max(f[n][0][i],f[n][1][i]));
    printf("%lld\n",ans);
    return;
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    T=read();
    while(T--){
        ans=0;
        n=read();
        for(int i=1;i<=n;i++) a[i]=read();
        a[0]=-1;
        if(n<=15){
            dfs(1);
            printf("%lld\n",ans);
        }else if(n<=2000){
            solve1();
        }
    }
    return 0;

}